1. Field of the Invention
The present invention relates to allocating electronic storage space for data storage.
2. Description of the Related Art
Data is placed on storage media, such as disk drives, in physical regions referred to as xe2x80x9cblocksxe2x80x9d. The storage system, such as a database or file system, essentially divides an object such as a file to be stored into block-sized portions, and then places them in the block-size regions of the disk drive. When a portion of a file is smaller than a block, the entire block nonetheless is allocated. The unused space in the block is referred to as xe2x80x9cinternal fragmentationxe2x80x9d.
Conventional allocation schemes such as those disclosed in Knuth, The Art of Computer Programming, vol. 1, Addison-Wesley Longman, Third Ed., 1998 allocate free space on an empty disk drive from first block to last block sequentially. This means that while initially, a file might be allocated a contiguous series of physical blocks, subsequent updates to the file will be placed in a disk region that is physically spaced from the remainder of the file by other blocks that have been recorded in the interim. This happens when, for instance, a point-in-time snapshot of a file system is to be made, with only changes to file blocks since the last snapshot being recorded. In such an instance, if an original block B of a three-block file has been changed to a modified block Bxe2x80x2, the original three blocks remain stored together as a record of the original version of the file, and the modified block Bxe2x80x2 is stored apart from the other blocks. Should a user subsequently desire to access the most recent version of the file, the system retrieves the two original unchanged blocks and the modified block Bxe2x80x2.
The present invention understands that a disk drive can read and deliver a single large read or write (say, 256 Kbytes long) in less time than it takes to perform two very much smaller operations. This is because the read head, which must move along the disk from one operation to the next, can be physically moved only so fast, with even a small movement generally consuming a large amount of time as compared to the time required to execute a single long read or write. For this reason, larger block sizes are advantageous. Competing with this, however, is the fact that smaller block sizes result in less internal fragmentation, i.e., less wasted space on the disk drive. That is, as block size increases, so does internal fragmentation.
With the above considerations in mind, the present invention critically observes that sequentially allocating free blocks on a disk can result in later versions of file blocks being stored apart from the remainder of the file, particularly in cases of point-in-time snapshots. Moreover, the present invention recognizes that large file blocks are desirable from a performance view, and that apart from the block size, it is desirable to minimize I/O operations, i.e., head movement. Accordingly, the present invention recognizes a need to provide a system in file blocks associated with a single file are generally stored contiguous to each other, even if written to disk at different times, which could otherwise result in data xe2x80x9csparsenessxe2x80x9d. The present invention also recognizes a need to minimize I/O operations when reading or writing file blocks when the blocks might not be exactly contiguous with each other. The solutions below have been provided to address one or more of the above-recognized needs.
A general purpose computer is programmed according to the inventive steps herein to allocate storage space in a storage system. The invention can also be embodied as an article of manufacturexe2x80x94a machine componentxe2x80x94that is used by a digital processing apparatus and which tangibly embodies a program of instructions that are executable by the digital processing apparatus to execute the present logic. This invention is realized in a critical machine component that causes a digital processing apparatus to perform the inventive method steps herein.
The invention can be implemented by a computer system including a data storage system having and a processor associated with a data storage system. The processor has logic for receiving a data object for storage, and randomly determining an original position on the storage medium to which to write the object. Updated blocks of the object are written in the original position or as close thereto as possible pursuant to, e.g., a copy-on-write operation of a point-in-time snapshot, or when data is written through multiple allocations. When an object is to be read from the medium, an entire region containing both the object and xe2x80x9cchaffxe2x80x9d data other than the object is read, with the xe2x80x9cchaffxe2x80x9d data being discarded subsequent to reading. The chaff can be discarded by a file subsystem, or prior to delivery to the subsystem by an input/output processor using a bit mask provided by the file subsystem.
In a preferred embodiment, the logic can determine a minimum desired data region density on the storage medium. Data is written into the region at least until the minimum desired data region density for the region is reached. The minimum desired data region density can be determined dynamically during system operation.
In another aspect, a computer program device includes a computer program storage device that is readable by a processor. A program is on the program storage device and includes instructions which can be executed by the processor for allocating space in a data storage system. The program includes computer readable code means for randomly determining, for each object, a start offset on a storage medium associated with the storage system. Computer readable code means write each object starting at its respective randomly determined start offset.
In still another aspect, a computer-implemented method for transferring data objects to and from a storage medium includes writing a first data object to a region of a data storage medium. A portion of a second object can be physically juxtaposed between two portions of the first object. The It first object is read along with the interposed portions of the second objects, and then subsequently the read portions of the second object are discarded.
The details of the present invention, both as to its structure and operation, can best be understood in reference to the accompanying drawings, in which like reference numerals refer to like parts, and in which: